// 解题思路：
// 题目要求重新排列条形码，保证相同的数不相邻
// 定义一个返回值数组，将条形码的重新排列放到里面
// 先处理出现次数最多的数，从 0 下标开始放，隔一个下标放一个
// 再处理剩下的数，接着上面的位置放，如果放到最后下标越界了，就回到数组下标 1 的位置开始放，直到放完所有的数

public class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int n = barcodes.length;
        int[] hash = new int[10001];

        for(int x : barcodes) hash[x]++;

        int max = 0;
        int maxPos = 1;
        for(int i = 1; i <= 10000; i++){
            if(max < hash[i]) {
                max = hash[i];
                maxPos = i;
            }
        }

        int[] ret = new int[n];
        int pos = 0;
        while(max-- > 0){
            ret[pos] = maxPos;
            pos += 2;
        }

        for(int i = 1; i <= 10000; i++){
            if(hash[i] != 0 && i != maxPos) {
                int key = i;
                int value = hash[i];
                while(value-- > 0){
                    if(pos >= n) pos = 1;
                    ret[pos] = key;
                    pos += 2;
                }
            }
        }

        return ret;
    }
}
